package com.leetcode.search;

import java.util.Arrays;

public class MaxSubArray {

    public int maxSubArray(int[] nums) {
        // if(nums.length == 0){
        // return 0;
        // }
        int pre = 0, ans = nums[0];
        for (int num : nums) {
            // 动态规划，每次迭代用一个值表示累积和，如果之前的累积和pre为正数的话就予以保留
            pre = Math.max(pre + num, num);
            ans = Math.max(ans, pre);
        }
        return ans;
    }

    /*
    * 返回最大子数组的索引范围
    */
    public int[] maxSubArray2(int[] nums) {
        int pre = 0, ans = nums[0];
        int start = 0;
        int[] res = new int[2];
        for (int i = 0; i < nums.length; i++) {
            if (pre > 0) {
                pre += nums[i];
            } else {
                pre = nums[i];
                start = i;
            }
            if (pre > ans) {
                ans = pre;
                res[0] = start;
                res[1] = i;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums = new int[] { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
        int res = new MaxSubArray().maxSubArray(nums);
        int[] res2 = new MaxSubArray().maxSubArray2(nums);
        System.out.println(res);
        System.out.println(Arrays.asList(res2[0], res2[1]));
    }
}
